package subject.tengxun.middle.easy;

/**
 * 功能：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 * 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
 * 输出：Intersected at '8'
 * 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
 * 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
 * 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
 * — 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
 * 作者：yedou
 * 日期：2024/7/3019:09
 */
public class getIntersectionNode {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) return null;

            // 计算两个链表的长度
            int lenA = length(headA), lenB = length(headB);
            // 将较长的链表的头指针移动到与较短的链表对齐的位置
            while (lenA > lenB) {
                headA = headA.next;
                lenA--;
            }
            while (lenB > lenA) {
                headB = headB.next;
                lenB--;
            }
            // 同时遍历两个链表，比较节点是否相同
            while (headA != headB) {
                headA = headA.next;
                headB = headB.next;
            }
            return headA; // 返回相交的节点，或者如果没有相交节点，则返回null
        }

        private int length(ListNode node) {
            int length = 0;
            while (node != null) {
                node = node.next;
                length++;
            }
            return length;
        }
    }

    public static ListNode method(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode pa = headA;
        ListNode pb = headB;
        // 我走过你走过的路，只会为了和你相遇
        while (pa != pb) {
            pa = pa == null ? headB : pa.next;
            pb = pb == null ? headA : pb.next;
        }
        return pa;
    }

    public static void main(String[] args) {
        int[] listA = {4, 1, 8, 4, 5};
        int[] listB = {5, 6, 1, 8, 4, 5};
        ListNode headA = createLinkedList(listA);
        ListNode headB = createLinkedList(listB);
        // 假设相交节点已经创建并链接到两个链表
        // 构造相交节点为值为8的节点
        headA.next.next = headB.next.next.next;

        Solution solution = new Solution();
        ListNode intersectionNode = solution.getIntersectionNode(headA, headB);
        if (intersectionNode != null) {
            System.out.println("Intersected at '" + intersectionNode.val + "'");
        } else {
            System.out.println("No intersection");
        }

        System.out.println(method(headA, headB).val);
    }

    private static ListNode createLinkedList(int[] values) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for (int value : values) {
            current.next = new ListNode(value);
            current = current.next;
        }
        return dummy.next;
    }
}
